﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WPFTrees.DataStructures
{
    // Node class 
    // http://codeidol.com/csharp/csharpckbk2/Data-Structures-and-Algorithms/Creating-an-n-ary-Tree/
    public class NTreeNode<U>
        where U : IComparable<U>
    {
        public NTreeNode(U value, int maxChildren)
        {
            if (value != null)
            {
                nodeValue = value;
            }

            childNodes = new NTreeNode<U>[maxChildren];
        }

        protected U nodeValue = default(U);
        protected NTreeNode<U>[] childNodes = null;

        #region my additions 
        int _leaves;

        public int Leaves { get { return _leaves; } set { _leaves = value; } }

        int _level=0;
        public int Level { get { return _level; } set { _level = value; } } 
        #endregion

        public int CountChildren
        {
            get
            {
                int currCount = 0;

                for (int index = 0; index <= childNodes.GetUpperBound(0); index++)
                {
                    if (childNodes[index] != null)
                    {
                        ++currCount;
                        currCount += childNodes[index].CountChildren;
                    }
                }

                return (currCount);
            }
        }

        public int CountImmediateChildren
        {
            get
            {

                int currCount = 0;

                for (int index = 0; index <= childNodes.GetUpperBound(0); index++)
                {
                    if (childNodes[index] != null)
                    {
                        ++currCount;
                    }
                }

                return (currCount);
            }
        }

        public NTreeNode<U>[] Children
        {
            get { return (childNodes); }
        }

        public NTreeNode<U> GetChild(int index)
        {
            return (childNodes[index]);
        }

        public U Value()
        {
            return (nodeValue);
        }

        public void AddNode(NTreeNode<U> node)
        {
            int numOfNonNullNodes = CountImmediateChildren;
            if (numOfNonNullNodes < childNodes.Length)
            {
                node.Level = this.Level + 1;
                childNodes[numOfNonNullNodes] = node;
            }
            else
            {
                throw (new Exception("Cannot add more children to this node."));
            }
        }
        public NTreeNode<U> DepthFirstSearch(U targetObj)
        {
            NTreeNode<U> retObj = default(NTreeNode<U>);

            if (targetObj.CompareTo(nodeValue) == 0)
            {
                retObj = this;
            }
            else
            {
                for (int index = 0; index <= childNodes.GetUpperBound(0); index++)
                {
                    if (childNodes[index] != null)
                    {
                        retObj = childNodes[index].DepthFirstSearch(targetObj);
                        if (retObj != null)
                        {
                            break;
                        }
                    }
                }
            }

            return (retObj);
        }
        public NTreeNode<U> BreadthFirstSearch(U targetObj)
        {
            Queue<NTreeNode<U>> row = new Queue<NTreeNode<U>>();
            row.Enqueue(this);

            while (row.Count > 0)
            {
                // Get next node in queue.
                NTreeNode<U> currentNode = row.Dequeue();

                // Is this the node we are looking for? 
                if (targetObj.CompareTo(currentNode.nodeValue) == 0)
                {
                    return (currentNode);
                }
                for (int index = 0;
                    index < currentNode.CountImmediateChildren;
                    index++)
                {
                    if (currentNode.Children[index] != null)
                    {
                        row.Enqueue(currentNode.Children[index]);
                    }
                }
            }

            return (null);
        }
        public void PrintDepthFirst()
        {
            Console.WriteLine("this: " + nodeValue.ToString());

            for (int index = 0; index < childNodes.Length; index++)
            {
                if (childNodes[index] != null)
                {
                    Console.WriteLine("\tchildNodes[" + index + "]: " +
                    childNodes[index].nodeValue.ToString());
                }
                else
                {
                    Console.WriteLine("\tchildNodes[" + index + "]: NULL");
                }
            }

            for (int index = 0; index < childNodes.Length; index++)
            {
                if (childNodes[index] != null)
                {
                    childNodes[index].PrintDepthFirst();
                }
            }
        }

        public List<U> IterateDepthFirst()
        {
            List<U> tempList = new List<U>();

            for (int index = 0; index < childNodes.Length; index++)
            {
                if (childNodes[index] != null)
                {
                    tempList.Add(childNodes[index].nodeValue);
                }
            }

            for (int index = 0; index < childNodes.Length; index++)
            {
                if (childNodes[index] != null)
                {
                    tempList.AddRange(childNodes[index].IterateDepthFirst());
                }
            }

            return (tempList);
        }
        public void RemoveNode(int index)
        {
            // Remove node from array and compact the array.
            if (index < childNodes.GetLowerBound(0) ||
                index > childNodes.GetUpperBound(0))
            {
                throw (new ArgumentOutOfRangeException("index", index,
                       "Array index out of bounds."));
            }
            else if (index < childNodes.GetUpperBound(0))
            {
                Array.Copy(childNodes, index + 1, childNodes, index,
                           childNodes.Length - index - 1);
            }
            childNodes.SetValue(null, childNodes.GetUpperBound(0));
        }
    }

}
